#include <stdlib.h>
#include <time.h>
#include <stdio.h>

#define ARRAY_SIZE 10

int partion(int arr[],int p,int r){
    int x = arr[r];
    int temp;
    int i=p-1;
    int j=p;
    for(j=p;j<r;j++){
        if(arr[j]<=x){
            i++;
            temp = arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    }
    temp = arr[i+1];
    arr[i+1]=x;
    arr[r]=temp;
    return i+1;
}

void quick_sort(int arr[],int p,int r){
    if(p<r){
        int q = partion(arr,p,r);
        quick_sort(arr,p,q-1);
        quick_sort(arr,q+1,r);
    }
}

void tail_recursive_quick_sort(int arr[],int p,int r){
    while(p<r){
        int q = partion(arr,p,r);
        tail_recursive_quick_sort(arr,p,q-1);
        p = q+1;
    }
}

int main(){
    int i = 0;
    int arr[ARRAY_SIZE+1];
    srand((unsigned)time(NULL));

    for(i=1;i<=ARRAY_SIZE;i++){
        arr[i] = rand()%1000;
    }


    printf("array [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",arr[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");
    tail_recursive_quick_sort(arr,1,ARRAY_SIZE);
    printf("array [");
    for(i=1;i<=ARRAY_SIZE;i++){
        printf("%d",arr[i]);
        if(i<ARRAY_SIZE){
            printf(",");
        }
    }
    printf("] \n");


    return 0;
}



